package leetcode.divide_and_conquer;

/**
 * @author mazouri
 * @create 2021-12-27 19:08
 */
public class _439_reversePairs {
    private int[] aux;//辅助数组
    private int count;

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        aux = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return count;
    }

    private void mergeSort(int[] nums, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }

    /**
     * 将num[lo...mid]和num[mid+1...hi]合并
     */
    private void merge(int[] nums, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {
            aux[k] = nums[k];
        }

        int m = i, n = j;
        while (m <= mid && n <= hi) {
            if ((long) nums[m] > 2 * (long) nums[n]) {
                count += (mid - m + 1);
                n++;
            } else {
                m++;
            }
        }

        //因为2倍的关系，不能直接放在里面计算，比如 2 3 4   1 5
        // 即使比较的那个不满足条件，后面的也可能满足条件 逆序对前面的不满足条件，后面的肯定不满足条件
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)         nums[k] = aux[j++];
            else if (j > hi)          nums[k] = aux[i++];
            else if (aux[i] > aux[j]) nums[k] = aux[j++];
            else                      nums[k] = aux[i++];
        }

    }

    public static void main(String[] args) {
        System.out.println(new _439_reversePairs().reversePairs(new int[]{2, 4, 3, 5, 1}));
    }
}
